import math
import random

def Kmeans(data, k, epsilon=1e-5, iteration=100):
    """
    K均值聚类主函数
    :param data: 输入数据，格式为列表嵌套列表，每个子列表是一个样本向量（如[[x1,y1], [x2,y2], ...]）
    :param k: 聚类数量
    :param epsilon: 收敛阈值（centroids变化量小于该值则停止迭代）
    :param iteration: 最大迭代次数（防止无限循环）
    :return: (clusters, centroids) 
             clusters: 聚类结果，列表，每个元素是对应样本的聚类标签（0~k-1）
             centroids: 最终聚类中心，列表嵌套列表
    """
    # 输入合法性检查
    if not data or k <= 0 or k > len(data):
        raise ValueError("数据不能为空，且k需满足 0 < k ≤ 样本数量")
    if not all(isinstance(sample, (list, tuple)) for sample in data):
        raise TypeError("每个样本必须是列表或元组类型的向量")
    sample_dim = len(data[0])
    if not all(len(sample) == sample_dim for sample in data):
        raise ValueError("所有样本必须具有相同的维度")
    
    # 1. 初始化聚类中心（随机选择k个不同的样本作为初始centroids）
    centroids = random.sample(data, k)
    # 转换为列表类型（确保可修改），并保留浮点数精度
    centroids = [list(map(float, centroid)) for centroid in centroids]
    
    iter_count = 0
    while iter_count < iteration:
        # 2. 分配聚类标签：为每个样本分配到最近的centroid
        clusters = [assign_cluster(sample, centroids) for sample in data]
        
        # 3. 更新聚类中心：计算每个聚类的均值作为新centroid
        new_centroids = []
        for cluster_id in range(k):
            # 收集当前聚类的所有样本
            cluster_samples = [data[i] for i in range(len(data)) if clusters[i] == cluster_id]
            if not cluster_samples:  # 防止空聚类（极端情况）
                new_centroids.append(centroids[cluster_id])  # 保留原中心
                continue
            # 计算每个维度的均值
            dim_means = []
            for dim in range(sample_dim):
                dim_sum = sum(sample[dim] for sample in cluster_samples)
                dim_means.append(dim_sum / len(cluster_samples))
            new_centroids.append(dim_means)
        
        # 4. 检查收敛：计算所有centroid的变化量（欧氏距离）
        centroid_changes = []
        for old_c, new_c in zip(centroids, new_centroids):
            dist = math.sqrt(sum((old - new)**2 for old, new in zip(old_c, new_c)))
            centroid_changes.append(dist)
        
        # 若所有中心变化量均小于epsilon，收敛并退出
        if max(centroid_changes) < epsilon:
            break
        
        # 否则更新centroids，继续迭代
        centroids = new_centroids
        iter_count += 1
    
    return clusters, centroids

def assign_cluster(x, c):
    """
    为单个样本x分配到最近的聚类中心
    :param x: 单个样本向量（列表/元组）
    :param c: 聚类中心列表（列表嵌套列表）
    :return: 最近聚类中心的索引（int，0~len(c)-1）
    """
    min_dist = float('inf')
    best_cluster = 0
    for cluster_id, centroid in enumerate(c):
        # 计算欧氏距离：sqrt(sum((x_i - c_i)^2))
        dist = math.sqrt(sum((xi - ci)**2 for xi, ci in zip(x, centroid)))
        if dist < min_dist:
            min_dist = dist
            dist = min_dist
            best_cluster = cluster_id
    return best_cluster